﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Graphs
{
    public class Graph
    {
        private int v;
        private int e;
        private List<int>[] adj; //邻接表(用List 代替  bag)

        /// <summary>
        /// 创建一个含有V个顶点但不含有边的图
        /// </summary>
        /// <param name="V"></param>
        public Graph(int V)
        {
            v = V;
            e = 0;
            adj = new List<int>[V];
            for (var i = 0; i < V; i++)
                adj[i] = new List<int>();
        }

        public Graph(string[] strs)
        {
            foreach (var str in strs)
            {
                var data = str.Split(' ');
                int v = Convert.ToInt32(data[0]);
                int w = Convert.ToInt32(data[1]);
                AddEdge(v,w);
            }
        }

        /// <summary>
        /// 顶点数
        /// </summary>
        /// <returns></returns>
        public int V()
        {
            return v;
        }

        /// <summary>
        /// 边数
        /// </summary>
        /// <returns></returns>
        public int E()
        {
            return e;
        }

        /// <summary>
        /// 向图中添加一条边 v-w
        /// </summary>
        /// <param name="v"></param>
        /// <param name="w"></param>
        public void AddEdge(int v, int w)
        {
            adj[v].Add(w);
            adj[w].Add(v);
            e++;
        }

        /// <summary>
        /// 和v相邻的所有顶点
        /// </summary>
        /// <param name="v"></param>
        /// <returns></returns>
        public IEnumerable<int> Adj(int v)
        {
            return null;
        }

        /// <summary>
        /// 计算 V 的度数
        /// </summary>
        /// <param name="G"></param>
        /// <param name="V"></param>
        /// <returns></returns>
        public static int Degree(Graph G, int V)
        {
            int degree = 0;
            foreach (int w in G.Adj(V))
                degree++;
            return degree;
        }

        /// <summary>
        /// 计算所有顶点的最大度数
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static int MaxDegree(Graph G)
        {
            int max = 0;
            for (int v = 0; v < G.V(); v++)
            {
                var d = Degree(G, v);
                if (d > max)
                    max = d;
            }
            return max;
        }

        /// <summary>
        /// 计算所有顶点的平均度数
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static double AvgDegree(Graph G)
        {
            return 2.0 * G.E() / G.V();
        }

        /// <summary>
        /// 计算自环的个数
        /// </summary>
        /// <param name="G"></param>
        /// <returns></returns>
        public static int NumberOfSelfLoops(Graph G)
        {
            int count = 0;
            for (int v = 0; v < G.V(); v++)
            {
                foreach (int w in G.Adj(v))
                {
                    if (v == w)
                        count++;
                }
            }

            return count / 2; //每条边都被计算了两次
        }

        public override string ToString()
        {
            string s = V() + " vertices, " + E() + " edges\n";
            for (int v = 0; v < V(); v++)
            {
                s += v + ":";
                foreach (int w in Adj(v))
                {
                    s += w + " ";
                }
                s += "\n";
            }
            return s;
        }
    }
}
